Trabajo Final de Lógica y Semánticas Formales (página 2)

4. Minimización De Funciones
Booleanas

El primer problema, al minimizar una función
dada, es decir, al encontrar la expresión "más
simple" que representa esta función,
es el de definir exactamente cuáles son los criterios para
determinar hasta qué punto una expresión es simple.
Llegar a esta definición no siempre es sencillo, pues se
pueden tener dos expresiones que representen la misma
función booleana, con el mismo número de
ocurrencias de cada variable y el mismo número de operaciones, con
lo cual ¿quién puede decir cual de las dos es la
más simple? El problema se hace aún más
complicado cuando se incrementa el número de operaciones
básicas, como es a menudo el caso, cuando queremos hallar
los valores de
alguna función.
Supondremos aquí que la "forma más simple"
significa la "forma más simple en forma normal
disyuntiva", y discutiremos la técnica de los mapas o diagramas de
Karnaugh. Como estamos trabajando en un álgebra
booleana, se podría realizar en teoría
una simplificación enteramente algebraica, utilizando las
leyes de
absorción y relaciones análogas. Pero la dificultad
estriba en estar seguro de que se
han tomado en cuenta todas las formas posibles de aplicar las
reglas simplificadoras. Las técnicas
que se han desarrollado para ayudar a la simplificación
son métodos de
ordenar la información sobre la función que
permita ver todas estas posibilidades.

Un diagrama de
Karnaugh es en realidad un diagrama de
Venn con las distintas regiones arregladas como cuadrados dentro
de un rectángulo. Como tales, tienen los mismos defectos
que tienen los diagramas de
Venn: para más de seis variables los
mapas de Karnaugh
se hacen demasiado complicados para que puedan ser útiles,
e incluso para cinco o seis variables
pierden ya mucha de su utilidad. Los
mapas de Karnaugh para de una a cuatro variables se presentan en
las figuras 1.1 a 1.4. Cada cuadrado representa el producto de
las coordenadas dadas sobre los bordes del rectángulo. Por
ejemplo, el cuadrado rotulado "a" en la figura 1.3 representa al
término x’yz y el rotulado con "b" en la figura 1.4
representa el término wx’y’z’. De
acuerdo con el axioma de conmutatividad, el orden de las letras
de variables no es importante.

Se conviene en que cada cuadrado, en un mapeo de
Karnaugh, contenga un "1", si el término representado por
ese cuadrado se requiere que esté presente en una
representación como suma de productos de
la función, o un "0" si el término ha de estar
ausente, o una "d" (de la expresión inglesa "don´t
care", "da lo mismo"), si la presencia o ausencia del
término es indiferente. Es frecuente no escribir
explícitamente los ceros.
El método
para el uso de un mapa tal, consiste en intentar cubrir todos los
1 con el menor número posible de rectángulos que
representan productos de
elementos.

Por ejemplo, en la figura 1.5 (donde se
usa un sistema
simplificado de coordenadas) los dos cuadrados marcados con "a"
representan el término wxy’z’ + wxyz’,
que pueden simplificarse a wxz’ por el uso de las leyes
distributivas. Análogamente, los cuadrados marcados con
"b" representan al término w’xy’, y los cuatro
cuadrados marcados con "c"corresponden al término yz. Sin
embargo, los dos cuadrados marcados con "d"corresponden a
wx’yz’ + w’x’y’z’, que no
pueden ser simplificados más. Y, en general, un grupo de tres
cuadrados, por ejemplo, no tiene ningún significado. Los
agrupamientos significativos siempre consisten en cuadrados
contiguos, con tal que consideremos los lados opuestos de los
mapas como continuos. Así, en la figura 1.6,
los

Cuadrados marcados "a", "b" y "c" representan,
respectivamente, los términos x’y’z, yz’
y y’z’. Dentro de éstas regiones cada cuadrado
debe contener o un 1 o una d. Ningún cuadrado puede
contener un 0, puesto que éstos representan
términos explícitamente excluidos; no todos los d
deben cubrirse, puesto que nos es indiferente que los
términos correspondientes estén o no presentes
Ejemplo A: Consideremos la función cuyo mapa K viene dado
en la figura 1.7. Hemos dibujado sobre este mapa tres
rectángulos que cubren los 1 y representan los
términos wxz’, xy y w’x’z. Nótese
que el cuadrado marcado "a" podría haberse usado por
sí mismo, pero, al combinarlo con el cuadrado que
está debajo de él, obtenemos el término
más simple wxz’ en lugar del wxy’z’.
Este cuadrado de más abajo del "a" está incluido en
los dos términos; pero no importa, por el axioma de
idempotencia. Los dos cuadrados marcados "b" representan el
producto
w’yz, pero no es necesario incluir este término ya
que los cuadrados están cubiertos por otros
términos.
Ejemplo B: Examinamos ahora una situación con
términos "indiferentes", que representamos en la figura
1.8. Tales términos pueden surgir porque, en una
aplicación particular, sabemos que ciertos productos nunca
aparecerán. Hemos mostrado aquí una cubierta de los
1, que representa la función por la expresión xz +
yz’. Nótese que tres de las d están tratadas
unos y las otras dos como ceros.

Fundamentos de la metodología
La metodología de simplificación de
funciones a
través de los diagramas de Karnaugh, a pesar de ser cuasi
intuitiva, está fundamentada a través del álgebra de
Boole, en la lógica
de proposiciones.
Como se ha visto anteriormente, se puede hacer una
correlación entre el álgebra de Boole, y la
lógica
proposicional. En la lógica, cada término de una
forma plena, representa una combinación de todas las
posibles de las variables. Del mismo modo, se puede trasladar
este concepto a los
mapas K, entendiendo que cada cuadrado interior, está
claramente identificado y al mismo tiempo se
diferencia de los otros, con una única combinación
de las variables (sin repetición) que contempla el mapa.
De este modo, el diagrama de n variables está contemplando
todas los posibles mintérminos de una forma plena de n
variables. En otras palabras, cada cuadrado interior de un
diagrama K de n variables representa una fila de una tabla de
verdad de una forma enunciativa de n variables.
El método
hace una asignación de valores a cada
celda del diagrama, según se necesite esté presente
o no en la fórmula a simplificar. En la lógica, se
puede interpretar este paso como la selección
de aquellos mintérminos que podrían resultar
verdaderos o falsos para alguna de todas las asignaciones
posibles.
Se continúa agrupando todos aquellos cuadrados que hallan
quedado marcados con un 1, y que estén en posiciones
contiguas o en los lados opuestos de un mapa, de tal forma que se
constituyan grupos de una
cantidad igual a una potencia de dos.
Esto debe ser así, ya que dos celdas con un lado en
común o dos celdas que se encuentran en lados opuestos de
un mapa, tienen como coordenadas las mismas variables, excepto
una. La variable en que se diferencia, aparece complementada en
una celda y sin complementar en la otra. Así, se puede
hacer uso de los axiomas de complementación, del elemento
neutro y de idempotencia; logrando como resultado la
simplificación de las dos celdas en cuestión a una
sola. Se puede realizar una interpretación similar para el
caso en que se trabaja con dos grupos de celdas.
Éstos grupos de celdas, deben contener un número de
celdas igual a una potencia de dos,
en forma similar a la estructura de
las columnas de una tabla de verdad, de manera que se pueda
aplicar el axioma de complementación. En las tablas de
verdad, una variable cambia el valor de su
asignación cada n veces, siendo n una potencia de dos. En
un grupo de n
celdas, la variable que se simplifica debe haber cambiado
2n-1 o menos veces su asignación, es decir,
debe poder ser
ubicada a la derecha de alguna/s otra/s en una tabla de verdad;
lo cual no sucedería si se eligieran grupos de celdas de
una cantidad distinta a la establecida.
El uso de asignaciones "don´t care" responde a un hecho
electrónico. Como la simplificación de funciones
booleanas se utiliza para el diseño
de circuitos, se
aclara que cada uno de estos circuitos
tiene una salida que se interpreta como un valor de
verdad igual a la salida de la función que calcula. Hay
ocasiones en que esta salida no importa para ciertas condiciones,
es decir para ciertas asignaciones para las variables, sea la que
fuere. En ese caso, es necesario tener una asignación que
permita sacar provecho de esta condición, para lo cual se
usa "d".

5.
Conclusión

La semejanza existente entre el álgebra booleana
y la lógica proposicional, nos permite realizar una
relación entre las funciones existentes en una y en otra.
Así, se pueden realizar métodos
para trabajar con funciones de boole, que resulten en una ayuda,
por ejemplo, para la etapa de diseño
del hardware de
una computadora
los cuales se basan en conceptos que se obtienen a partir del
desarrollo de
las dos áreas.
El método presentado es de mucha utilidad cuando
se trabaja con pocas variables, pero deja de serlo cuando este
número crece. Se deja como sugerencia para algún
otro trabajo, el análisis de técnicas
alternativas para un número mayor de variables, como
podría ser el desarrollado por W. V. Quine y E. J.
McCluskey Jr.; o en todo caso, la creación de algoritmos con
esta finalidad.

6.
Bibliografía

• Libros:
• • Naishtat, Francisco S.

"Lógica para Computación" – Editorial Eudeba, Buenos
Aires. ã
1986
Páginas: 99 – 100

• Korfhage, Robert

"Lógica y Algoritmos" –
Editorial Limusa Wesley – D.F. México. ã 1970
Páginas: 31 – 43

• Trejo, César A.

"Matemática
Elemental Moderna" – Editorial Eudeba, Buenos
Aires. ã
1968
Páginas: 189 – 193

• Grassmann, Winfried Karl,

Tremblay, Jean-Paul
"Matemática
Discreta y Lógica" – Editorial Prentice Hall,
Madrid. ã
1996
Páginas: 34 – 38, 110 – 112

• Hamilton, A. G.

"Lógica para matemáticos" – Editorial
Paraninfo, Madrid. ã 1981
Páginas: 9 – 28

• Internet:
• • http://www.mat.usach.cl/histmat/html/bool.html.

Autor:

Leonardo Arias Paz
Santiago del Estero, Argentina